/**
 * Created with IntelliJ IDEA.
 * Description:
 * User:何人亮
 * Date:2024-07-11
 * 21:54
 */
public class  SingleLinkedList implements Ilist{
    public static class MySingleLinkedList{
        int val;
        MySingleLinkedList next;

        public MySingleLinkedList(int val) {
            this.val = val;
        }
    }

    MySingleLinkedList head;
    @Override
    public void addFirst(int data) {
        if(head==null){
            MySingleLinkedList mySingleLinkedList1=new MySingleLinkedList(data);
            head=mySingleLinkedList1;
        }else{
            MySingleLinkedList mySingleLinkedList=new MySingleLinkedList(data);
            mySingleLinkedList.next=head;
            head=mySingleLinkedList;
        }
    }

    @Override
    public void addLast(int data) {
        MySingleLinkedList mySingleLinkedList=new MySingleLinkedList(data);
        if(head==null){
            head=mySingleLinkedList;
        }else {
            MySingleLinkedList cur=head;
            while (cur.next!=null){
                cur=cur.next ;
            }
            cur.next=mySingleLinkedList;
        }
    }

    @Override
    public void addIndex(int index, int data) {
        int len=size();
        if(index<0||index>len){
            System.out.println("位置不合法");
            return;
        }
        if(index==0){
            addFirst(data);
            return;
        }if(index==len){
            addLast(data);
            return;
        }
        MySingleLinkedList cur=head;
        MySingleLinkedList indexdata=new MySingleLinkedList(data);
        while (index-1!=0){
            cur=cur.next;
            index--;
        }
        indexdata.next=cur.next;
        cur.next=indexdata;
    }

    @Override
    public boolean contains(int key) {
        MySingleLinkedList cur= head;
        if(cur==null){
            return false;
        }
        while (cur!=null){
            if (cur.val==key){
                return true;
            }else{
                cur=cur.next;
            }
        }
        return false;
    }

    @Override
    public void remove(int key) {
        if(head==null) {
            return;
        }
        if(contains(key)==false){
            System.out.println("要删除的key不存在");
            return;
        }
        MySingleLinkedList cur=head;
        if(head.val==key){
            head=head.next;
            return;
        }
      while (cur.next.val!=key ){
          cur=cur.next;
      }
      cur.next=cur.next.next;
    }

    @Override
    public void removeAllKey(int key) {
        if(head==null){
            return;
        }if (contains(key)==false){
            System.out.println("不存在key" );
            return;
        }
        MySingleLinkedList cur=head.next;
        MySingleLinkedList prev=head;
        while (cur!=null){
            if(cur.val==key){
                prev.next=cur.next;
                cur=cur.next;
            }else{
                cur=cur.next;
                prev=prev.next;
            }
        }
        if(head.val==key){//前面已经删除了除第一个节点外的是key的节点，所以最后检查一下头节点即可
            head=head.next;
        }
    }

    @Override
    public int size() {
        int len=0;
        MySingleLinkedList cur=head;
        while(cur!=null){
            cur=cur.next;
            len++;
        }
        return len;
    }

    @Override
    public void display() {
        if(head==null){
            System.out.println("链表为空");
            return ;
        }
        MySingleLinkedList cur=head;
        while (cur!=null){
            System.out.print(cur.val+" ");
            cur=cur.next;
        }
        System.out.println();
    }

    @Override
    public void clear() {
        //head=null;//简单粗暴的置空方法
        //温柔一点的置空方法
        MySingleLinkedList cur=head;
        MySingleLinkedList curN=cur.next;
        while (cur!=null){
            cur.next=null   ;
            cur=curN;
            if(curN!=null) {
                curN = curN.next;
            }
        }
        head=null;
    }



    public static boolean chkPalindrome(SingleLinkedList.MySingleLinkedList A) {//判断链表是不是回文
        // write code here
        if(A==null){
            return true;
        }
        SingleLinkedList.MySingleLinkedList slow=A;
        SingleLinkedList.MySingleLinkedList fast=A;
        while(fast!=null&&fast.next!=null){
            fast=fast.next.next;
            slow=slow.next;
        }//循环后slow是中间节点
        SingleLinkedList.MySingleLinkedList cur=slow.next;
        SingleLinkedList.MySingleLinkedList curN=cur.next;
        while(cur!=null){
            cur.next=slow;
            slow=cur;
            cur=curN;
            if(curN!=null){
                curN=curN.next;
            }
        }
        while(slow!=A){
            if(slow.val!=A.val){
                return false;
            }
            if(A.next==slow){
                return true;
            }
            slow=slow.next;
            A=A.next;
        }
        return true;
    }
}

